package gold.digger;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC315 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public class AverageTreeNode {
            public AverageTreeNode left;
            public AverageTreeNode right;
            public int count;
            public int val;

            public AverageTreeNode(int val, AverageTreeNode left, AverageTreeNode right, int count) {
                this.left = left;
                this.right = right;
                this.count = count;
                this.val = val;
            }
        }

        public class LessFinder {
            public AverageTreeNode root;

            public void addNum(int num) {
                this.root = addNumByRecur(this.root, num);
            }

            public AverageTreeNode addNumByRecur(AverageTreeNode root, int num) {
                if (root == null) {
                    return new AverageTreeNode(num, null, null, 1);
                }

                root.count += 1;
                if (root.val > num) {
                    root.left = addNumByRecur(root.left, num);
                } else {
                    root.right = addNumByRecur(root.right, num);
                }

                return root;
            }

            public int findLess(int val) {
                addNum(val);
                return findLessRecur(this.root, val, 0);
            }

            public int findLessRecur(AverageTreeNode root, int val, int alreadyCount) {
                if (null == root) return alreadyCount;

                if (root.val == val) {
                    return null == root.left ? alreadyCount : alreadyCount + root.left.count;
                }

                if (val < root.val) {
                    return findLessRecur(root.left, val, alreadyCount);
                } else {
                    alreadyCount += null == root.left ? 1 : root.left.count + 1;
                    return findLessRecur(root.right, val, alreadyCount);
                }
            }
        }


        public List<Integer> countSmaller(int[] arr) {
            List<Integer> res = new ArrayList<>();
            LessFinder lf = new LessFinder();
            for (int i = arr.length - 1; i >= 0; i--) {
                res.add(lf.findLess(arr[i]));
            }

            Collections.reverse(res); //使用方法进行逆序
            return res;
        }
    }

    public boolean run() {
        Solution su = new Solution();
        int[] arr = {5, 2, 6, 1};
        System.out.println(su.countSmaller(arr));

        return true;
    }

    public static void main(String[] args) throws Exception {
        LC315 an = new LC315();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
